import java.util.*;

//最大滑动窗口，窗口长度固定，求所有最大窗口和
public class MaxSlidingWindow {
}
class MaxSlidingWindowSolution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n-k+1];
        Deque<Integer> que = new LinkedList();
        int index = 0;
        for(int i=0;i<n;i++){
            while(!que.isEmpty()&&nums[que.peekFirst()]<nums[i])
                que.pollFirst();
            que.addFirst(i);
            if(que.peekLast()<=(i-k))
                que.pollLast();
            if(i-k>=-1)
                res[index++] = nums[que.peekLast()];
        }
        return res;
    }
}

//两个滑动窗口最大值，相邻窗口一起滑动，左窗口记录截至当前最大和，右窗口实时更新与左窗口最大和的和
class TwoWindowsSolution{
    int[] maxTwoSum(int[] nums,int k){
        int[] ans = new int[2];
        int sum1 = 0,maxSum1 = 0,maxSum1Idx = 0;
        int sum2 = 0,maxSum2 = 0;
        for(int i=k;i<nums.length;i++){
            sum1+=nums[i-k];//左窗口从[0,k-1]开始
            sum2+=nums[i];//右窗口从[k,2k-1]开始
            //开始滑动
            if(i>=k*2-1){
                if(sum1>maxSum1){//维护左窗口最大值和对应起始点
                    maxSum1 = sum1;
                    maxSum1Idx = i-k*2+1;
                }
                if(maxSum1+sum2>maxSum2){//维护右窗口最大值和对应起始点
                    maxSum2 = maxSum1 + sum2;
                    ans[0] = maxSum1Idx;
                    ans[1] = i-k+1;
                }
                //左右窗口删除过期元素
                sum1 -=nums[i-k*2+1];
                sum2 -=nums[i-k+1];
            }
        }
        return ans;
    }
}

//三个滑动窗口最大值，第一个滑动窗口最大和首索引自己更新，
//第二个滑动窗口最大和更新同时将前两个首索引一起更新，保证不重叠
class ThreeWindowsSolution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int[] ans = new int[3];
        int sum1 = 0,maxSum1 = 0,maxSum1Idx = 0;
        int sum2 = 0,maxSum2 = 0,maxSum21Idx = 0,maxSum22Idx = 0;
        int sum3 = 0,maxSum3 = 0,maxSum3Idx = 0;
        for(int i=2*k;i<nums.length;i++){
            sum1+=nums[i-2*k];
            sum2+=nums[i-k];
            sum3+=nums[i];
            if(i>=k*3-1){
                if(sum1>maxSum1){
                    maxSum1 = sum1;
                    maxSum1Idx = i-3*k+1;//第一个滑动窗口首索引更新
                }
                if(maxSum1+sum2>maxSum2){
                    maxSum2 = maxSum1+sum2;
                    maxSum21Idx = maxSum1Idx;//第二个滑动窗口更新时再将第一个首索引更新到结果，保证不重叠
                    maxSum22Idx = i-2*k+1;
                }
                if(maxSum2+sum3>maxSum3){
                    maxSum3 = maxSum2+sum3;
                    ans[0] = maxSum21Idx;//最终索引结果
                    ans[1] = maxSum22Idx;
                    ans[2] = i-k+1;
                }
                sum1-=nums[i-k*3+1];
                sum2-=nums[i-k*2+1];
                sum3-=nums[i-k+1];
            }
        }
        return ans;
    }
}
